<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">
 <meta>
  <!-- Stylesheets -->
  <link href="../web.css" type="text/css" rel="stylesheet"></link>
  <link href="../pygmentize.css" type="text/css" rel="stylesheet"></link>
  <title>VLFeat - Tutorials - kd-tree</title>
  

  <!-- Scripts-->
  
 </meta>

 <!-- Body Start -->
 <body>
  <div id="header">
   <!-- Google CSE Search Box Begins -->
   <form action="http://www.vlfeat.org/search.html" method="get" id="cse-search-box" enctype="application/x-www-form-urlencoded">
    <div>
     <input type="hidden" name="cx" value="003215582122030917471:oq23albfeam"></input>
     <input type="hidden" name="cof" value="FORID:11"></input>
     <input type="hidden" name="ie" value="UTF-8"></input>
     <input type="text" name="q" size="31"></input>
     <input type="submit" name="sa" value="Search"></input>
    </div>
   </form>
   <script src="http://www.google.com/coop/cse/brand?form=cse-search-box&amp;lang=en" xml:space="preserve" type="text/javascript"></script>
   <!-- Google CSE Search Box Ends -->
   <h1><a shape="rect" href="../index.html" class="plain"><span id="vlfeat">VLFeat</span><span id="dotorg">.org</span></a></h1>
  </div>
  <div id="headbanner">
   Tutorials - kd-tree
  </div>
  <div id="pagebody">
   <div id="sidebar"> <!-- Navigation Start -->
    <ul>
<li><a href="../index.html">Home</a>
</li>
<li><a href="../download.html">Download</a>
</li>
<li><a href="../doc.html">Documentation</a>
</li>
<li><a href="tut.html">Tutorials</a>
<ul>
<li><a href="sift.html">SIFT</a>
</li>
<li><a href="dsift.html">DSIFT/PHOW</a>
</li>
<li><a href="mser.html">MSER</a>
</li>
<li><a href="ikm.html">IKM</a>
</li>
<li><a href="hikm.html">HIKM</a>
</li>
<li><a href="aib.html">AIB</a>
</li>
<li><a href="quickshift.html">Quick shift</a>
</li>
<li><a href="slic.html">SLIC</a>
</li>
<li><a href="kdtree.html" class='active' >kd-tree</a>
</li>
<li><a href="imdisttf.html">Distance transf.</a>
</li>
<li><a href="utils.html">Utils</a>
</li>
</ul></li>
<li><a href="../applications/apps.html">Applications</a>
</li>
</ul>

   </div> <!-- sidebar -->
   <div id="content">
      

<p><b>VLFeat</b> implements the randomized kd-tree forest from
<a shape="rect" href="http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN">FLANN</a>.
This enables fast medium and large scale nearest neighbor
queries among high dimensional data points (such as those produced by SIFT).
</p>

<ul>
  <li><a shape="rect" href="kdtree.html#tut.kdtree.introduction">Introduction</a></li>
  <li><a shape="rect" href="kdtree.html#tut.kdtree.querying">Querying</a></li>
  <li><a shape="rect" href="kdtree.html#tut.kdtree.forest">Randomized kd-tree forests</a></li>
</ul>

<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->
<h1 id="tut.kdtree.introduction">Introduction</h1>
<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->

<p>A kd-tree is a data structure used to quickly solve
nearest-neighbor queries. Consider a set of 2D points uniformly
distributed in the unit square:</p>

<div class="highlight"><pre>  <span class="n">X</span> <span class="p">=</span> <span class="nb">rand</span><span class="p">(</span>2<span class="p">,</span> 100<span class="p">)</span> <span class="p">;</span>
</pre></div>


<p>A kd-tree is generated by using the <code>vl_kdtreebuild</code> function:
</p>

<div class="highlight"><pre>  <span class="n">kdtree</span> <span class="p">=</span> <span class="n">vl_kdtreebuild</span><span class="p">(</span><span class="n">X</span><span class="p">)</span> <span class="p">;</span>
</pre></div>


<p>The returned <code>kdtree</code> indexes the set of
points <code>X</code>. Given a query point <code>Q</code>, the
function <code>vl_kdtreequery</code> returns its nearest neighbor
in <code>X</code>:</p>

<div class="highlight"><pre>  <span class="n">Q</span> <span class="p">=</span> <span class="nb">rand</span><span class="p">(</span>2<span class="p">,</span> 1<span class="p">)</span> <span class="p">;</span>
  <span class="p">[</span><span class="n">index</span><span class="p">,</span> <span class="n">distance</span><span class="p">]</span> <span class="p">=</span> <span class="n">vl_kdtreequery</span><span class="p">(</span><span class="n">kdforest</span><span class="p">,</span> <span class="n">X</span><span class="p">,</span> <span class="n">Q</span><span class="p">)</span> <span class="p">;</span>
</pre></div>


<p>Here <code>index</code> stores the index of the column
of <code>X</code> that is closest to the point <code>Q</code>.
<code>distance</code> is the squared euclidean distance between <code>X(index),Q</code>.</p>

<p>A kd-tree is a hierarchal structure built by partitioning the data
recursively along the dimension of maximum variance. At
each iteration the variance of each column is computed and the data is
split into two parts on the column with maximum variance. The
splitting threshold can be selected to be the mean or the median (use
the <code>ThresholdMethod</code> option of
<code>vl_kdtreebuild</code>).</p>

<div class="figure">
 <img src="../demo/kdtree_uniform_mean.jpg"></img>
 <img src="../demo/kdtree_uniform_median.jpg"></img>
 <div class="caption">
  <span class="content">
   kd-tree partitions of a uniform set of data points, using
   the mean (left image) and the median (right image) thresholding
   options of <code>vl_kdtreebuild</code>. On the bottom right corner
   a query point is marked along with the ten closest neighbors as
   found by <code>vl_kdtreequery</code>. Figure generated
   by <code>vl_demo_kdtree</code>.
  </span>
 </div>
</div>

<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->
<h1 id="tut.kdtree.querying">Querying</h1>
<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->

<p><code>vl_kdtreequery</code> uses a best-bin first search
heuristic. This is a branch-and-bound technique that maintains an
estimate of the smallest distance from the query point to any of the
data points down all of the open paths.</p>

<p><code>vl_kdtreequery</code> supports two important operations:
  <em>approximate nearest-neighbor search</em> and <em>k-nearest
  neighbor search</em>. The latter can be used to return the 
  <em>k</em> nearest neighbors to a given query point <code>Q</code>.
  For instance:
</p>

<div class="highlight"><pre><span class="p">[</span><span class="n">index</span><span class="p">,</span> <span class="n">distance</span><span class="p">]</span> <span class="p">=</span> <span class="n">vl_kdtreequery</span><span class="p">(</span><span class="n">kdtree</span><span class="p">,</span> <span class="n">X</span><span class="p">,</span> <span class="n">Q</span><span class="p">,</span> <span class="s">&#39;NumNeighbors&#39;</span><span class="p">,</span> 10<span class="p">)</span> <span class="p">;</span>
</pre></div>


<p>returns the closest 10 neighbors to <code>Q</code>
in <code>X</code> and their distances, stored along the columns of
<code>index</code> and <code>distance</code>.</p>

<p>The <code>MaxComparisons</code> option is used to run an ANN query.
The parameter specifies how many paths in the best-bin-first search of
the kd-tree can be checked before giving up and returning the closest
point encountered so far. For instance:</p>

<div class="highlight"><pre><span class="p">[</span><span class="n">index</span><span class="p">,</span> <span class="n">distance</span><span class="p">]</span> <span class="p">=</span> <span class="n">vl_kdtreequery</span><span class="p">(</span><span class="n">kdtree</span><span class="p">,</span> <span class="n">X</span><span class="p">,</span> <span class="n">Q</span><span class="p">,</span> <span class="s">&#39;NumNeighbors&#39;</span><span class="p">,</span> 10<span class="p">,</span> <span class="s">&#39;MaxComparisons&#39;</span><span class="p">,</span> 15<span class="p">)</span> <span class="p">;</span>
</pre></div>


<p>does not compare any point in <code>Q</code> with more than 15
points in <code>X</code>.</p>

<div class="figure">
 <img src="../demo/kdtree_ann_1.jpg"></img>
 <img src="../demo/kdtree_ann_2.jpg"></img>
 <img src="../demo/kdtree_ann_3.jpg"></img>
 <img src="../demo/kdtree_ann_4.jpg"></img>
 <div class="caption">
  <span class="content">
    Finding the 10 approximated nearest neighbors for increasing
    values of the <code>MaxComparisons</code> parameter. Note that at
    most <code>MaxComparisons</code> neighbors can be returned (if more
    are requested, they are ignored). Figure generated
    by <code>vl_demo_kdtree_ann</code>.
  </span>
 </div>
</div>

<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->
<h1 id="tut.kdtree.forest">Randomized kd-tree forests</h1>
<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->

<p>VLFeat supports constructing randomized <em>forests</em> of
kd-trees to improve the effectiveness of the representation in high
dimensions. The parameter <code>NumTrees</code> of
<code>vl_kdtreebuild</code> specifies how many trees to use in
constructing the forest. Each tree is constructed independently.
Instead of always splitting on the maximally variant dimension, each
tree chooses randomly among the top five most variant dimensions at
each level. When querying, <code>vl_kdtreequery</code> runs
best-bin-first across all the trees in parallel. For instance</p>

<div class="highlight"><pre>  <span class="n">kdtree</span> <span class="p">=</span> <span class="n">vl_kdtreebuild</span><span class="p">(</span><span class="n">X</span><span class="p">,</span> <span class="s">&#39;NumTrees&#39;</span><span class="p">,</span> 4<span class="p">)</span> <span class="p">;</span>
  <span class="p">[</span><span class="n">index</span><span class="p">,</span> <span class="n">distance</span><span class="p">]</span> <span class="p">=</span> <span class="n">vl_kdtreequery</span><span class="p">(</span><span class="n">kdtree</span><span class="p">,</span> <span class="n">X</span><span class="p">,</span> <span class="n">Q</span><span class="p">)</span> <span class="p">;</span>
</pre></div>


<p>constructs four trees and queries them.</p>

<div class="figure">
 <img src="../demo/kdtree_forest_tree_1.jpg"></img>
 <img src="../demo/kdtree_forest_tree_2.jpg"></img>
 <img src="../demo/kdtree_forest_tree_3.jpg"></img>
 <img src="../demo/kdtree_forest_tree_4.jpg"></img>
 <div class="caption">
  <span class="content">
    The parameter <code>NumTrees</code>
    tells <code>vl_kdtreebuild</code> to construct a number of
    randomized kd-trees. Figure generated
    by <code>vl_demo_kdtree_forest</code>.
  </span>
 </div>
</div>



   </div>
   <div class="clear">&nbsp;</div>
  </div> <!-- pagebody -->
  <div id="footer">
   &copy; 2007-12 Andrea Vedaldi and Brian Fulkerson
  </div> <!-- footer -->

  <!-- Google Analytics Begins -->
  <script xml:space="preserve" type="text/javascript">
   //<![CDATA[
    var localre = /vlfeat.org/;
    if(document.location.host.search(localre) != -1)
    {
   var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
   document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
   }
   //]]>
  </script>
  <script xml:space="preserve" type="text/javascript">
    //<![CDATA[
    var localre = /vlfeat.org/;
    if(document.location.host.search(localre) != -1)
    {

   try {
   var pageTracker = _gat._getTracker("UA-4936091-2");
   pageTracker._trackPageview();
   } catch(err) {}

   }
   //]]>
  </script>
  <!-- Google Analytics Ends -->
 </body>
</html>

 